
#ifndef __MULTCONJACOTADO_H__
#define __MULTCONJACOTADO_H__

//Servicios usados
#include "../aed2/TiposBasicos.h"
#include "../aed2/Arreglo.h"

namespace aed2{
	class MultConjAcotado{
	public:

		class const_Iterador;
		class const_Iterador_Unicos;

         /**
         * Crea un multiconjunto vacío con la cota especificada
         *
         * PRE : Ninguna
         * POST: Se crea el multiconjunto.
         *
         * @Parametros: Cota
         * @Devuelve: Nada
         */ 
		MultConjAcotado(Nat cota);
		
         /**
         * Crea un multiconjunto que es copia del primero
         *
         * PRE : Ninguna
         * POST: Se crea el multiconjunto.
         *
         * @Parametros: Multiconjunto
         * @Devuelve: Nada
         */ 
		MultConjAcotado(const MultConjAcotado& mconj);

         /**
         * Libera la memoria asignada por el multiconjunto
         *
         * PRE : Ninguna
         * POST: Se libera la memoria asignada.
         *
         * @Parametros: Nada
         * @Devuelve: Nada
         */ 
		~MultConjAcotado();
		

        /**
        * Agrega al multiconjunto una determinada cantidad de repeticiones de un elemento
        *
        * PRE : elemento es menor a la cota
        * POST: La cantidad de repeticiones del elemento en el multiconjunto aumenta de 
        * 		acuerdo a la cantidad especificada.
        *
        * @Parametros: elemento, cantidad
        * @Devuelve: Nada
        */ 
		void Agregar(Nat elemento, Nat cantidad);

		/**
        * Qutia al multiconjunto una determinada cantidad de repeticiones de un elemento
        *
        * PRE : elemento es menor a la cota
        * POST: La cantidad de repeticiones del elemento en el multiconjunto disminuye de
        * 		acuerdo a la cantidad especificada, siendo esta siempre mayor o igual a 0.
        *
        * @Parametros: elemento, cantidad
        * @Devuelve: Nada
        */ 
		void Quitar(Nat elemento, Nat cantidad);

		/**
        * Testea la pertenencia de un elemento al multiconjunto.
        *
        * PRE : Ninguna.
        * POST: Se devuelve un bool con el valor de verdad de la relación de pertenencia.
        *
        * @Parametros: elemento
        * @Devuelve: true si elemento pertenece al muticonjunto, false en otro caso
        */ 
		bool Pertenece(Nat elemento) const;

		/**
        * Devuelve la cantidad de elementos del multiconjunto
        *
        * PRE : Ninguna.
        * POST: Se devuelve la cantidad de elementos del multiconjunto.
        *
        * @Parametros: Ninguno
        * @Devuelve: Cantidad de elementos del multiconjunto
        */ 
		Nat Cardinal() const;
		
		/**
        * Devuelve la cantidad de repeticiones de un elemento en el multiconjunto
        *
        * PRE : Ninguna.
        * POST: Se devuelve la cantidad de repeticiones de un elemento en el multiconjunto
        *
        * @Parametros: elemento
        * @Devuelve: Cantidad de elementos del multiconjunto, si el elemento no está en el multiconjunto, devuelve 0
        */ 
		Nat Cardinal(Nat elemento) const;

		/**
        * Devuelve un elemento perteneciente al multiconjunto con la menor cantidad de repeticiones
        *
        * PRE : El multiconjunto no es vacío
        * POST: Se devuelve el mínimo, si hay varios, se devuelve el elemento con el mayor valor.
        * 		Ej. Si 5 y 7 son elementos mínimos del multiconjunto, ambos con 3 repeticiones, se devuelve el 7.
        *
        * @Parametros: Ninguno
        * @Devuelve: Elemento con la mínima cantidad de repeticiones
        */ 
		Nat Minimo() const;

		/**
        * Devuelve la cantidad de elementos distintos del multiconjunto
        *
        * PRE : Ninguna.
        * POST: Se devuelve la cantidad de elementos distintos del multiconjunto
        *
        * @Parametros: Ninguno
        * @Devuelve: Cantidad de elementos distintos
        */ 
		Nat CantDistintos() const;
		
		/**
        * Devuelve un iterador constante al conjunto de elementos distintos del multiconjunto
        *
        * PRE : Ninguna.
        * POST: Se devuelve el iterador
        *
        * @Parametros: Ninguno
        * @Devuelve: const_Iterador_Unicos
        */ 
		const_Iterador_Unicos Conj() const;
	
		/*CrearIt() crea un iterador constante, no modificable, que itera los elementos distintos del multiconjunto.
		 * Los elementos no están ordenados, pero el primer elemento del iterador es aquel con la menor cantidad de 
		 * repeticiones en el multiconjunto.
		 * Queda invalidado si, luego de la creación del iterador, el multiconjunto es modificado. */
		const_Iterador CrearIt() const;
		
		class const_Iterador {
                public:
                	const_Iterador() {}
                    const_Iterador(const MultConjAcotado::const_Iterador& otro) : conj(otro.conj), pos(otro.pos) {}
                    const_Iterador& operator=(const MultConjAcotado::const_Iterador& otro){
						conj = otro.conj; 
						pos = otro.pos;
						return *this;
					}
                    
                    //dos iteradores son iguales si iteran el mismo conjunto y se encuentran en la misma posición
                    bool operator==(const MultConjAcotado::const_Iterador& otro) const {
						return conj == otro.conj && pos == otro.pos;
						}
                    
                    bool HaySiguiente() const;
                    bool HayAnterior() const;
                    Nat Siguiente() const;
                    Nat CardinalSiguiente() const;
                    Nat Anterior() const;
                    Nat CardinalAnterior() const;
                    void Avanzar();
                    void Retroceder();

                protected:
                    const_Iterador(const MultConjAcotado* conjunto);
                private:
                    friend MultConjAcotado::const_Iterador MultConjAcotado::CrearIt() const;
                    const MultConjAcotado* conj;
                    Nat pos;
		};

		class const_Iterador_Unicos : public const_Iterador {

		private:

			const_Iterador_Unicos(const MultConjAcotado* conjunto) :
				const_Iterador(conjunto) {
			}

			friend MultConjAcotado::const_Iterador_Unicos MultConjAcotado::Conj() const;
            Nat CardinalSiguiente() const;
            Nat CardinalAnterior() const;
		};


	private:

		//el operador de asignación está anulado
		MultConjAcotado & operator=(const MultConjAcotado & mconj);

		Arreglo<Nat>* repeticiones;
		Arreglo<Nat>* posiciones;
		Arreglo<Nat>* heap;
		Nat pos_libre;
		Nat cardinal;
		
		//Operaciones auxiliares
		
		//EliminarRaiz(in/out this : multconjAcotado)
		void EliminarRaiz();
		
		//Subir(in/out this : multconjAcotado, Nat pos)
		void Subir(Nat pos);
		
		//Prioridad(in this : multconjAcotado, Nat elemento)
		Nat Prioridad(Nat elemento) const;
		
		//Padre(in this : multconjAcotado, Nat i)
		Nat Padre (Nat i) const;
		
		//Bajar(in/out this : multconjAcotado, Nat pos)
		void Bajar(Nat pos);
		
		void IntercambiarPosiciones(Nat i, Nat j);
	};

	std::ostream& operator<<(std::ostream& os, const MultConjAcotado&);
}
#endif /* __MULTCONJACOTADO_H__ */

